# -*- coding: utf-8 -*-
# Created by zhangyanqi on 2018/5/1

"""
构造哈夫曼树

思路：
将两个最小的合并,形成新的树结点
注意：哈夫曼树没有度为1的结点
"""
from LeetCode.初级算法.树.遍历二叉树 import in_order_traversal_recursion
from  LeetCode.初级算法.树.遍历二叉树 import pre_order_traversal_recursion

class Node(object):
    def __init__(self, val, l=None, r=None):
        self.val = val
        self.left = l
        self.right = r

    def __str__(self):
        return str(self.val)


def build(nodes):
    nodes = sorted(nodes, key=lambda x: x.val)
    while len(nodes) >= 2:
        node1 = nodes.pop(0)
        node2 = nodes.pop(0)
        new_node = Node(node1.val + node2.val, node1, node2)
        nodes.append(new_node)
        nodes = sorted(nodes, key=lambda x: x.val)
    return nodes[0]



if __name__ == "__main__":
    build1 = build([Node(3), Node(2), Node(1)])
    in_order_traversal_recursion(build1)
    print("========")
    pre_order_traversal_recursion(build1)
